public class Sort {

    public static int[] insertSort(int[] arr) {   //直接插入排序
        for (int i = 1; i < arr.length; i++) {
            for (int j = i - 1; j >= 0; j--) {
                int tmp = arr[j + 1];
                if (arr[j + 1] < arr[j]) {
                    arr[j + 1] = arr[j];
                    arr[j] = tmp;
                } else {
                    break;
                }
            }
        }
        return arr;
    }

    public static int[] xiErSort(int[] array) {
        int gap = array.length;
        while (gap > 1) {
            xiEr(array, gap);
            gap /= 2;
        }
        xiEr(array, 1);
        return array;
    }

    public static void xiEr(int[] arr, int gap) {

        for (int i = gap; i < arr.length; i++) {
            int tmp = arr[i];
            int j = i - gap;
            for (; j >= 0; j -= gap) {
                if (arr[j] > tmp) {
                    arr[j + gap] = arr[j];
                    arr[j] = tmp;

                } else {
                    break;
                }
            }

        }
    }

    //选择排序
    public static void xuanZeSort(int[] array) {
        int left = 0;
        int right = array.length - 1;

        while (left < right) {
            int maxdex = left;
            int mindex = left;
            for (int i = left + 1; i <= right; i++) {
                if (array[i] < array[mindex]) {
                    mindex = i;
                } else {
                    maxdex = i;
                }
            }
            if (maxdex != left) {
                int tmp = array[mindex];
                array[mindex] = array[left];
                array[left] = tmp;
                tmp = array[maxdex];
                array[maxdex] = array[right];
                array[right] = tmp;
            } else {
                int tcp = array[left];
                int tmp = array[mindex];
                array[mindex] = array[left];
                array[left] = tmp;
                array[right] = tcp;
            }
            left++;
            right--;
        }
    }


    //创建大根堆
    public static void creatMap(int[] array) {
        for (int parent = (array.length - 1 - 1) / 2; parent >= 0; parent--) {
            shiftDown(array, parent, array.length);
        }
    }

    //向下调整为
    private static void shiftDown(int[] array, int parent, int usedSize) {
        int child = 2 * parent + 1;
        while (child < usedSize) {
            if (child + 1 < usedSize && array[child] < array[child + 1]) {
                child++;
            }
            if (array[child] > array[parent]) {
                int tmp = array[parent];
                array[parent] = array[child];
                array[child] = tmp;
                parent = child;
                child = 2 * parent + 1;
            } else {
                break;
            }
        }
    }

    //堆排序
    public static void mapSort(int[] array) {
        int end = array.length - 1;
        while (end > 0) {
            int tmp = array[0];
            array[0] = array[end];
            array[end] = tmp;
            end--;
            shiftDown(array, 0, end + 1);
        }
    }

    public static void mergeSort(int[] array) {
        mergeSortFunc(array, 0, array.length - 1);
    }

    public static void mergeSortFunc(int[] array, int left, int right) {
        if (left >= right) {
            return;
        }
        int mid = (left + right) / 2;
        mergeSortFunc(array, left, mid);
        mergeSortFunc(array, mid + 1, right);
        merge(array, left, right, mid);
    }

    public static void merge(int[] array, int start, int end, int mid) {

        int s1 = start;
        int s2 = mid + 1;
        int[] tmp = new int[end - start + 1];
        int k = 0;
        while (s1 <= mid && s2 <= end) {
            if (array[s1] < array[s2]) {
                tmp[k++] = array[s1++];
            } else {
                tmp[k++] = array[s2++];
            }
        }
        while (s1 <= mid) {
            tmp[k++] = array[s1++];
        }
        while (s2 <= end) {
            tmp[k++] = array[s2++];
        }
        for (int i = 0; i < tmp.length; i++) {
            array[i + start] = tmp[i];
        }
    }

    public static void mergeSort1(int[] array) {
        int gap = 1;
        while (gap < array.length) {
            for (int i = 0; i < array.length; i += gap * 2) {
                int left = i;
                int mid = left + gap - 1;
                if (mid >= array.length) {
                    mid = array.length - 1;
                }
                int right = mid + gap;
                if (right >= array.length) {
                    right = array.length - 1;
                }
                merge(array, left, right, mid);
            }
            gap *= 2;
        }
    }


    //挖坑法，left为基准的，然后划分递归
    public static void quickSort(int[] array) {
              quick(array,0,array.length-1);

    }

    public static void quick(int[] array, int start, int end) {
        if (start >= end) {
            return;
        }
        int pivot = parection(array, start, end);
        quick(array, start, pivot - 1);
        quick(array, pivot + 1, end);

    }

    public static int parection(int[] array, int left, int right) {

        int tmp = array[left];
        while (left < right) {
            while (left < right && array[right] >= tmp) {
                right--;
            }
            array[left] = array[right];

            while (left < right && array[left] <= tmp) {
                left++;
            }
            array[right] = array[left];
        }
        array[left]=tmp;
        return left;
    }

    //rigth要找到比基准小的
    //left要找到比基准大的


    //hoare法
    public static int parection1(int[] array, int left, int right) {

        int tmp = array[left];
        int i=left;
        while (left < right) {
            while (left < right && array[right] >= tmp) {
                right--;
            }

            while (left < right && array[left] <= tmp) {
                left++;
            }
            int tcp=array[left];
            array[left]=array[right];
            array[right]=tcp;
        }

       int tap=array[i];
        array[i]=array[left];
        array[left]=tap;
        return left;
    }

}
